#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[2][10010], tmp[10010];
char s[200610], q[10010];
int n, m;
int ans[200010];
int main(){
	int t;
	scanf("%d", &t);
	for (int TT=1;TT<=t;TT++){
		scanf("%d%d%s%s", &n, &m, s, q);
		memset(dp, 0, sizeof(dp));
		memset(ans, 0, sizeof(ans));
		dp[0][0]=dp[1][0]=1;
		for (int i=1;i<=n;i++){
			memset(tmp, 0, sizeof(tmp));
			tmp[0]=1;
			if (s[i-1]==q[0]) tmp[1]=1;
			for(int j=2;j<=min(i, m);j++)
				if (dp[1][j-1] && s[i-1]==q[j-1]) tmp[j]=1;
				else if (dp[0][j-2] && i>1 && s[i-2]==q[j-1] && s[i-1]==q[j-2])
					tmp[j]=1;
			if (i >= m) {
				if (tmp[m]) ans[i-m]=1;
				else ans[i-m]=0;
			}
			memcpy(dp[0], dp[1], sizeof(dp[0]));
			memcpy(dp[1], tmp, sizeof(tmp));
		}
		for (int i=0;i<n;i++) printf("%d", ans[i]);
		printf("\n");
	}
}

